import java.util.Arrays;
import java.util.Random;

class Sort{

    //插入排序
    public static void insertSort(int[] array){
        for (int i=1;i<array.length;i++){
            int tmp=array[i];
            int j=i-1;
            for (;j>=0;j--){
                if (array[j]>tmp){
                   array[j+1]=array[j];
                }else {
                    break;
                }
            }
            array[j+1]=tmp;
        }
    }

    //希尔排序
    public static void shellSort(int[] array){
        int group= array.length/3+1;
         while (group>=1){
             groupSort(array,group);
             if (group==1)
                 break;
             group=group/3+1;
         }
    }

    private static void groupSort(int[] arr,int group){
        for (int i=group;i< arr.length;i++){
            int tmp=arr[i];
            int j=i-group;
            for (;j>=0;j=j-group){
                if (arr[j]>tmp){
                    arr[j+group]=arr[j];
                }else {
                    break;
                }
            }
            arr[j+group]=tmp;
        }
    }

    //选择排序
    public static void selectSort(int[] arr){

        int left=0;
        int right= arr.length-1;
        int max,min;
        while (left<right){
            max=left;
            min=right;
            for (int i=left;i<=right;i++){
                if (arr[i]>arr[max]){
                    max=i;
                }
                if(arr[i]<arr[min]){
                    min=i;
                }
            }

            swap(arr,left,min);
            if (max==left){
                max=min;
            }
            swap(arr,max,right);

            left++;
            right--;

        }

    }

    //堆排序
    public static void heapSort(int[] arr){

        int lastans= (arr.length-2)/2;
        while(lastans>=0){
            adjustdown(arr,lastans ,arr.length);

            lastans--;
        }

        for (int i=arr.length-1;i>0;i--){
            swap(arr,0,i);
            adjustdown(arr,0,i);
        }

    }


    private static void adjustdown(int[]arr,int root,int size){

        int child=root*2+1;
        while(child<size){
            if (child+1<size&&arr[child+1]>arr[child]){
                child++;
            }
            if (arr[root]<arr[child]){
                swap(arr,root,child);
            }
            root=child;
            child=root*2+1;
        }

    }


    public static void bubbleSort(int arr[]){
        for (int i=0;i< arr.length-1;i++){
            boolean hs=true;
            for (int j=0;j< arr.length-1-i;j++){
                if (arr[j]>arr[j+1]){
                    hs=false;
                    swap(arr,j,j+1);
                }
            }
            if(hs)
                break;
        }
    }


    public static void quickSort(int[] arr){
        qsort(arr,0, arr.length-1);
    }

    private static void qsort(int[] arr,int left,int right){
        if (left>=right)
            return;
        int cen=sortrcen(arr,left,right);
        qsort(arr,left,cen-1);
        qsort(arr,cen+1,right);
    }

    private static int sortrcen(int[] arr,int left,int right){
        if (left==right)
            return left;
        int tmp=arr[left];
        while (left<right){
            while(left<right&&arr[right]>tmp){
                right--;
            }
            while(left<right&&arr[left]<tmp){
                left++;
            }
            swap(arr,left,right);
            if (left!=right&&arr[left]==arr[right])
                left++;
        }
        arr[left]=tmp;
        return left;
    }

    private static void swap(int[] arr,int p1,int p2){
        int temp=arr[p1];
        arr[p1]=arr[p2];
        arr[p2]=temp;

    }


}

















public class Main {
    public static void main(String[] args) {

        Random random=new Random();
        int[] num1=new int[10];
        int[] num2=new int[10];

        int[] bignum1=new int[100000];
        int[] bignum2=new int[100000];

        for (int i=0;i< num1.length;i++){
            num2[i]=num1[i]= random.nextInt(100);
        }

        for (int i=0;i<bignum1.length;i++){
            bignum2[i]=bignum1[i]= random.nextInt(1000000);
        }

        System.out.println("排序前：");
        System.out.println(Arrays.toString(num1));
        System.out.println();

        Sort.insertSort(num1);
        System.out.println("插入排序后：");
        System.out.println(Arrays.toString(num1));
        System.out.print("运行参考时间：");
        long t1=System.currentTimeMillis();
        Sort.insertSort(bignum1);
        long t2=System.currentTimeMillis();
        System.out.println(t2-t1+" ms");
        System.out.println();

        num1=Arrays.copyOf(num2,num2.length);
        bignum1=Arrays.copyOf(bignum2,bignum2.length);

        Sort.shellSort(num2);
        System.out.println("希尔排序后：");
        System.out.println(Arrays.toString(num2));
        System.out.print("运行参考时间：");
        t1=System.currentTimeMillis();
        Sort.shellSort(bignum2);
        t2=System.currentTimeMillis();
        System.out.println(t2-t1+" ms");
        System.out.println();

        num2=Arrays.copyOf(num1,num1.length);
        bignum2=Arrays.copyOf(bignum1,bignum1.length);

        Sort.selectSort(num2);
        System.out.println("选择排序后：");
        System.out.println(Arrays.toString(num2));
        System.out.println("运行参考时间：");
        t1=System.currentTimeMillis();
        Sort.selectSort(bignum2);
        t2=System.currentTimeMillis();
        System.out.println(t2-t1+" ms");
        System.out.println();

        num2=Arrays.copyOf(num1,num1.length);
        bignum2=Arrays.copyOf(bignum1,bignum1.length);

        Sort.heapSort(num2);
        System.out.println("堆排序后：");
        System.out.println(Arrays.toString(num2));
        System.out.println("运行参考时间：");
        t1=System.currentTimeMillis();
        Sort.heapSort(bignum2);
        t2=System.currentTimeMillis();
        System.out.println(t2-t1+" ms");
        System.out.println();

        num2=Arrays.copyOf(num1,num1.length);
        bignum2=Arrays.copyOf(bignum1,bignum1.length);

        Sort.bubbleSort(num2);
        System.out.println("冒泡排序后：");
        System.out.println(Arrays.toString(num2));
        System.out.println("运行参考时间：");
        t1=System.currentTimeMillis();
        Sort.bubbleSort(bignum2);
        t2=System.currentTimeMillis();
        System.out.println(t2-t1+" ms");
        System.out.println();

        num2=Arrays.copyOf(num1,num1.length);
        bignum2=Arrays.copyOf(bignum1,bignum1.length);

        Sort.quickSort(num2);
        System.out.println("快速排序后：");
        System.out.println(Arrays.toString(num2));
        System.out.println("运行参考时间：");
        t1=System.currentTimeMillis();
        Sort.quickSort(bignum2);
        t2=System.currentTimeMillis();
        System.out.println(t2-t1+" ms");
        System.out.println();


    }

    public static void main2(String[] args) {
        int[] num={84, 83, 10, 83, 51, 54, 46, 59, 12, 53};
        System.out.println(Arrays.toString(num));
        Sort.quickSort(num);
        System.out.println(Arrays.toString(num));
    }

    public static void main1(String[] args) {
        int[] num={37, 96, 2, 15, 49, 26, 42, 92, 75, 70};

        Sort.heapSort(num);
        System.out.println(Arrays.toString(num));
    }

}